package 队列;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/implement-queue-using-stacks/
 *
 * 使用栈实现队列的下列操作：
 * push(x) -- 将一个元素放入队列的尾部。
 * pop() -- 从队列首部移除元素。
 * peek() -- 返回队列首部的元素。
 * empty() -- 返回队列是否为空。
 *
 * 示例:
 * MyQueue queue = new MyQueue();
 * queue.push(1);
 * queue.push(2);
 * queue.peek();  // 返回 1
 * queue.pop();   // 返回 1
 * queue.empty(); // 返回 false
 *
 * 思路: 使用两个栈，入队栈和出队栈
 * 1. 数据入队，直接放到入队栈
 * 2. 数据出队，直接从出队栈顶获取数据，若无数据，将入队栈的数据全部push到出队栈中，再从栈顶出数据
 * 3. 数据出队，若出队栈和入队栈均无数据，则无相关数据
 */
public class _232_用栈实现队列 {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.push(1);
        queue.push(2);
        System.out.println(queue.peek());
        System.out.println(queue.pop());
        System.out.println(queue.empty());
        System.out.println(queue.pop());
        System.out.println(queue.empty());
    }
}

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    /**
     * 初始化数据
     */
    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    /**
     * 入队
     */
    public void push(int x) {
        inStack.push(x);
    }

    /**
     * 出队
     */
    public int pop() {
        handingData();
        return outStack.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        handingData();
        return outStack.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return outStack.isEmpty() && inStack.isEmpty();
    }

    public void handingData() {
        if (empty()) {
            throw new RuntimeException("no elements");
        }
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                Integer item = inStack.pop();
                outStack.push(item);
            }
        }
    }
}
